#include<iostream>
#include<windows.h>
#include<stdlib.h>
#include<cstring>
using namespace std;
const int N = 5000005;
float nums[N];
float res;
void sum1(int n) {
    float sum=0;
    for (int i = 0; i < n; ++i)sum += nums[i];
    res = sum;
}
void sum2(int n) {
    float sum1 = 0, sum2 = 0;
    for (int i = 0; i < n; i += 2) {
        sum1 += nums[i];
        sum2 += nums[i + 1];
    }
    res = sum1 + sum2;
}
void sum3(int n) {
    if (n == 1)return;
    for (int i = 0; i < n / 2; ++i)
        nums[i] += nums[n - i - 1];
    sum3(n / 2);
}
void sum4(int n) {
    for (int m = n; m > 1; m /= 2)
        for (int i = 0; i < m / 2; ++i)
            nums[i] = nums[i * 2] + nums[i * 2 + 1];
    res = nums[0];
}
int main() {
    long long head, tail, freq;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
    int  cnt = 0;
    cout << "-------the first-----------" << endl;
    for (int n = 16; n <N; n *= 2) {
        QueryPerformanceCounter((LARGE_INTEGER*)&head);
        do {
            for (int i = 0; i <n; ++i)nums[i]=i+1;
            sum1(n);
            QueryPerformanceCounter((LARGE_INTEGER*)&tail);
            ++cnt;
        } while (tail - head < 20000);
        long long time_used = (tail - head) * 1000 / freq;
        printf("%d & %d & %d\\\\\n", n, cnt, time_used);
        cnt = 0;
    }
    cnt = 0;
    cout << "-------the second---------" << endl;
    for (int n = 16; n <N; n *= 2) {
        QueryPerformanceCounter((LARGE_INTEGER*)&head);
        do {
            for (int i = 0; i < n; ++i)nums[i] = i + 1;
            sum2(n);
            QueryPerformanceCounter((LARGE_INTEGER*)&tail);
            ++cnt;
        } while (tail - head < 20000);
        long long time_used = (tail - head) * 1000 / freq;
        printf("%d & %d\\\\\n", cnt, time_used);
        cnt = 0;
    }
    cnt = 0;
    cout << "-------the third---------" << endl;
    for (int n = 16; n <N; n *= 2) {
        QueryPerformanceCounter((LARGE_INTEGER*)&head);
        do {
            for (int i = 0; i < n; ++i)nums[i] = i + 1;
            sum3(n);
            QueryPerformanceCounter((LARGE_INTEGER*)&tail);
            ++cnt; 
        } while (tail - head < 20000);
        long long time_used = (tail - head) * 1000 / freq;
        printf("%d & %d\\\\\n", cnt, time_used);
        cnt = 0;
    }
    cnt = 0;
    cout << "-------the forth---------" << endl;
    for (int n = 16; n <N; n *= 2) {
        QueryPerformanceCounter((LARGE_INTEGER*)&head);
        do {
            for (int i = 0; i < n; ++i)nums[i] = i + 1;
            sum4(n);
            QueryPerformanceCounter((LARGE_INTEGER*)&tail);
            ++cnt;
        } while (tail - head < 20000);
        long long time_used = (tail - head) * 1000 / freq;
        printf("%d & %d\\\\\n", cnt, time_used);
        cnt = 0;
    }
    cnt = 0;
}
